//威佐夫博奕
//wythoff_game.cpp

//A和B两人轮流从两堆物品中取出一些物品
//每次取至少1个物品，多则不限
//每次可以单独从其中一堆物品中取物品，也可以同时从两堆物品中取数量相同的物品
//最后一个将两堆物品取光的人获胜

//1)局势
//当A面临(0, 0)局势时，A已经输了，因为B已经把两堆物品取光，称(0, 0)是最终局势
//当A面临(1, 2)局势时，A也必然输了，A取后B必然能够一次把两堆物品取光
//当A面临(3, 5)局势时，A也必然输了，A取后B虽然存在无法一次就把两堆物品取光的情况
//比如A取后局势变为(3, 4)，但B可以在两堆中同时取2个使局势变为(1, 2)，A还是输了
//这样必然输的局势称为奇异局势(Cold Position)，用(a(k), b(k))表示，k为局势下标非负整数
//最终局势(0, 0)也属于奇异局势
//其中a(k)与b(k)交换位置后仍然是等价的，为了方便设a(k) <= b(k)
//前几个奇异局势是：
//k  0  1  2  3  4  5  6  7  8  9  ...
//a  0  1  3  4  6  8  9  11 12 14 ...
//b  0  2  5  7  10 13 15 18 20 23 ...
//即(a(0), b(0)) = (0, 0)，k = 0
//(a(1), b(1)) = (1, 2)，k = 1
//(a(2), b(2)) = (3, 5)，k = 2
//...
//
//2)局势的性质
//性质1：
//任何自然数都包含于且仅包含于一个奇异局势中
//且a(k) > a(k-1)，b(k) > b(k-1)，b(k) = a(k) + k
//性质2：
//任意操作都可以将奇异局势改变为非奇异局势(Hot Position)
//性质3：
//通过适当的方法可以将非奇异局势变为奇异局势
//
//3)计算奇异局势序列
//原始的计算方法是初始k = 0时a(0) = 0，b(0) = 0
//以后递归的计算k = 1，k = 2，k = 3...的情况
//对于k = i，a(i)取之前0到i-1中尚未使用的最小自然数作为a(i)的值，而b(i) = a(i) + i
//比如对于：
//k  0  1  2  3  4  5  6  7  8  9  
//a  0  1  3  4  6  8  9  11 12 14 
//b  0  2  5  7  10 13 15 18 20 23 
//当k = 10时，a(10)取从0到9中尚未使用过的最小自然数16，b(10) = 16 + 10 = 26
//
//更快的方式是用黄金分割方法，由威佐夫(Wythoff)提出，该算法也由他的名字命名
//黄金分割Golden Ratio是x^2 = x + 1的正值解，设t为根号5，则黄金分割为(1+t)/2
//从黄金分割有：
//k						0  1	  2		 3	    4	   5	  6		
//k*golden_ratio		0  1.618  3.236  4.854  6.472  8.090  9.708
//a						0  1	  3	     4		6	   8	  9
//k*(golden_ratio+1)	0  2.618  5.236  7.854  10.472 13.090 15.708
//b						0  2	  5		 7		10	   13	  15
//则可以得到结论，对于i >= 0，a(i)取小于i*golden_ratio的最大整数
//其中i*golden_ratio一定是一个无理数，大于a(i)小于a(i)+1
//
//4)局势变换策略
//从上文可知令对手处于奇异局势(a(k), b(k))即可获胜
//因此获胜关键在于将非奇异局势转化为奇异局势
//非奇异局势(a, b)有5种情况：
//a = b						第1种情况
//a = a(k), b > b(k)		第2种情况
//a = a(k), b < b(k)		第3种情况
//第1种情况：
//将a和b两堆同时取完，令对方面临(0, 0)奇异局势
//第2种情况：
//从b中取b - b(k)数量的物品，使b = b(k)，令对方面临(a(k), b(k))奇异局势
//第3种情况：
//i)若b > a，这时必然存在这样一个t = b - a，从a和b中同时取a - a(t)数量的物品
//因为有b(k) = a(k) + k，则有b - (a - a(t)) = b - a + a(t) = b - a + b(t) - t = b(t)
//同时取出a - a(t)物品后使a = a(t)，b = b(t)，令对方面临(a(t), b(t))奇异局势
//ii)若b < a，则不能b - a，因为本文问题中都是非负整数的计算
//则需求出b在奇异局势数组中的下标k'
//从a中取a - a(k')个物品，使a = a(k')，令对方面临(a(k'), b(k'))奇异局势
//
//网络上流行的中文文档中关于这里的情况划分通常是5种
//但其中第3种情况的讲解非常糟糕，因为网络文档中将局势中a和b的下标k搞混，容易令人误解
//经过总结本文将5种情况进行了筛选，经过测试是正确的
//
//本文引用了“Wythoff’s Game”，作者“Kimberly Hirschfeld-Cotton(Oshkosh, Nebraska)”

#include "general_head.h"
int get_a2k(int a);
int get_b2k(int b);

bool wythoff_game(int a, int b, int& get_a, int& get_b)
{//两堆物品的数量分别为a和b
 //判断是否有胜算，若有胜算则返回从a和b中取的物品数量get_a和get_b
	//若a = b，直接同时取完令对方面临(0, 0)奇异局势
	if(a == b){
		get_a = a;
		get_b = b;
		return(true);
	}

	//黄金分割1.618
	double golden_ratio = (1 + pow((double)5, (double)0.5)) / 2;	
	//通过a求出其在奇异局势数组中a的对应下标k
	int k = get_a2k(a);
	//将k带回黄金分割法的公式求出a(k)
	//比较k求出的a(k)与a是否相等来验证函数输入的a是否就是奇异函数数组中的a
	//若a = a(k)则a就是a(k)，否则这个a不是奇异局势数组中的a，而是颠倒顺序的b
	//比如在奇异局势数组中：
	//k  0  1  2  3  4  5  6  7  8  9  
	//a  0  1  3  4  6  8  9  11 12 14 
	//b  0  2  5  7  10 13 15 18 20 23 
	//若a是一个颠倒的b，比如a = 2时，通过上述计算出的k = 2
	//再带回黄金分割法得到的ak = 3与原本的a = 2不相等
	//若a = 5，计算出k = 4，带回黄金分割得到ak = 6与原本a = 5不相等
	//而若a = 1，计算出k = 1，带回黄金分割得到ak = 1与原本的a = 1相等
	int ak = (int)(k * golden_ratio);
	if(ak != a)
		//若求出的ak与原本的a不相等
		//则将两堆物品a和b颠倒顺序，注意取物品的数量get_a和get_b位置也交换
		return(wythoff_game(b, a, get_b, get_a));

	//若求出的ak = a
	//则说明该a就是奇异局势数组中的a，b就是奇异局势数组中的b，而不是颠倒情况
	//计算b(k) = a(k) + k
	int bk = a + k;
	if(b == bk)
		//a = a(k)，b = b(k)，则当前两堆物品已经满足a(k)和b(k)的奇异局势，直接认输
		return(false);
	else if(b > bk){
		//b > b(k)，从b中取b - b(k)个物品，使b = b(k)
		get_a = 0;
		get_b = b - bk;
		return(true);
	}
	else{
		//b < b(k)
		if(b >= a){
			//从a和b中同时取出a - a(t)个物品，使a = a(t)，b = b(t)
			int t = b - a;
			int at = (int)(t * golden_ratio);
			get_a = a - at;
			get_b = a - at;
		}
		else{
			//b < a
			int k2 = get_b2k(b);
			int ak2 = k2 * golden_ratio;
			get_a = a - ak2;
			get_b = 0;
		}
		return(true);
	}
}
int get_a2k(int a)
{//通过a逆向求出k
	//黄金分割1.618
	double golden_ratio = (1 + pow((double)5, (double)0.5)) / 2;	
	//物品数量a可能是奇异局势数组中某个a(k)，也可能不是
	//但此处先假设该a就是奇异局势数组中下标为k处的a(k)
	//通过a(k)为小于k*golden_ratio的最大整数来逆向计算a在奇异局势数组中的下标k
	double p = a / golden_ratio;
	int k = (int)p + 1;
	return(k);
}
int get_b2k(int b)
{//通过b逆向求出k
	double golden_ratio = (1 + pow((double)5, (double)0.5)) / 2;
	//b(k)为小于k*(golden_ratio+1)的最大整数
	double p = b / (golden_ratio + 1);
	int k = (int)p + 1;
	return(k);
}
